<?php
/**
 * User: LRZ
 * Date: 2020/3/2
 * Time: 17:10
 */

/**
 *  443.压缩字符串
 *
 *  标签：字符串
 *
 *  给定一组字符，使用原地算法将其压缩。
 *  压缩后的长度必须始终小于或等于原数组长度。
 *  数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
 *  在完成原地修改输入数组后，返回数组的新长度。
 *
 *  进阶：你能否仅使用O(1) 空间解决问题？
 *
 *  示例 1：
 *      输入：["a","a","b","b","c","c","c"]
 *      输出：返回6，输入数组的前6个字符应该是：["a","2","b","2","c","3"]
 *      说明："aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。
 *
 *  示例 2：
 *      输入：["a"]
 *      输出：返回1，输入数组的前1个字符应该是：["a"]
 *      说明：没有任何字符串被替代。
 *
 *  示例 3：
 *      输入：["a","b","b","b","b","b","b","b","b","b","b","b","b"]
 *      输出：返回4，输入数组的前4个字符应该是：["a","b","1","2"]。
 *      说明：由于字符"a"不重复，所以不会被压缩。"bbbbbbbbbbbb"被“b12”替代。注意每个数字在数组中都有它自己的位置。
 *
 *  注意：
 *      所有字符都有一个ASCII值在[35, 126]区间内。
 *      1 <= len(chars) <= 1000。
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/string-compression
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$chars = ['a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b'];
$res   = compress($chars);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function compress(&$chars)
{
    $length = count($chars);
    $anchor = 0; # 锚点，连续字符串的起始位置
    $write  = 0; # 数组写的位置
    foreach ($chars as $read => $readValue) {
        # 当前元素与下一个元素不等时，执行以下代码
        if ($read + 1 === $length || $chars[$read + 1] !== $readValue) {
            # 从write指针开始写入
            $chars[$write++] = $chars[$anchor];
            # 当前位置大于锚点位置时，表示有连续的字符串，计算出字符串的个数，并往write指针所指的空间写入长度字符（假设长度是12，就要写入1和2）
            if ($read > $anchor) {
                $nums = (string)($read - $anchor + 1);
                for ($i = 0, $iLength = strlen($nums); $i < $iLength; $i++) {
                    $chars[$write++] = $nums[$i];
                }
            }
            $anchor = $read + 1;
        }
    }
    return $write;
}